This invention relates to a method and apparatus for finding the error locator polynomial required for decoding a Reed-Solomon (RS) code, and more particularly to an efficient, VLSI implementable, time or transform domain RS decoder.
By this invention, both the errata locator and errata evaluator polynomials can be obtained simultaneously and simply by the Euclidean algorithm. With these ideas, the complexity of both the time and transform domain Reed-Solomon decoders for correcting errors and erasures can be simplified. As a consequence, decoders for correcting errors and erasures of Reed-Solomon codes can be made more modular, regular, simple, and naturally suitable for VLSI implementation.
The Euclidean algorithm for solving the key equation for decoding BCH and Goppa type codes was disclosed by Sugiyama, et al., in Y. Sugiyama, M. Kasahara, S. Hirasawa and T. Namekawa, "A method for solving key equation for decoding Goppa codes," IEEE Trans. on Contr., vol. 27, 1975, pp. 87-99. A fast decoding of RS codes using continued fraction which is closely related to the Euclidean algorithm was disclosed by I. S. Reed, R. A. Scholtz, T. K. Truong and L. R. Welch, "The fast decoding of Reed-Solomon codes using Fermat theoretic transforms and continued fractions," IEEE Trans. on Information Theory, vol. IT-24, no. 1, January 1978., and L. R. Welch and R. A. Scholtz, "Continued fractions and Berlekamp's algorithm," IEEE Trans. on Information Theory, vol. IT-25, 1979, pp. 19-27. Brent and Kung in "Systolic VLSI arrays for polynomial GCD computation," IEEE Trans. on Computers, vol. C-33, no. 8, August 1984, pp. 731-736, were the first to suggest a systolic array architecture for computing the greatest common divisor (GCD) of two polynomials. By the use of the above ideas, a pipeline structure for a transform domain decoder was developed to decode errors of RS codes. See H. M. Shao, T. K. Truong, L. J. Deutsch, J. H. Yuen and I. S. Reed, "A VLSI design of a pipeline Reed-Solomon decoder," IEEE Trans. on Computers, vol. C-34, no. 5, May 1985. An important ingredient of this design was a modified Euclidean algorithm for computing the error-locator polynomial.
The computation of inverse field elements is completely avoided in the above-mentioned modification of Euclid's algorithm. Recently, it was proposed that a recursive algorithm could be used to perform this modified Euclidean algorithm. H. M. Shao, T. K. Truong, I. S. Hsu, L. J. Deutsch and I. S. Reed, "A single chip VLSI Reed-Solomon decoder," presented at International Conference on Acoustics, Speech and Signal Processing, ICASSP, Tokyo, Japan, Apr. 7-11, 1986. An important advantage of that new recursive algorithm is that the entire systolic array needed to perform Euclid's algorithm requires substantially less silicon area than the pipeline version of the modified Euclidean algorithm, given in IEEE Trans. on Computers, May 1985, cited above.
Forney defined in "On decoding BCH codes," IEEE Trans. on Information Theory, vol. IT-11, 1965, pp. 549-557, an errata locator polynomial using what are now called Forney syndromes to correct both errors and erasures. Blahut showed, in Theory and Practice of Error Control Codes, Addison-Wesley Publishing Co., CA, May 1984, pp. 258, that the errata locator polynomial can be computed directly by initializing Berlekamp's algorithm with the erasure locator polynomial.
Recently W. L. Eastman, "Decoding erasures," The Mitre Corporation Report, Bedford, MA, 1986 suggested that the errata evaluator polynomial can be computer directly by initializing Berlekamp's algorithm with the Forney syndrome polynomial. By this technique, it is possible to compute the errata locator polynomial and the errata evaluator polynomial simultaneously from the Euclidean algorithm. This new RS decoder uses both the erasure locator polynomial and the Forney syndrome polynomial as initial conditions for the Euclidean algorithm.
It is shown and proved by T. K. Truong, W. L. Eastman, I. S. Reed, and I. S. Hsu, "A simplified procedure for correcting both errors and erasures of a Reed-Solomon code using the Euclidean algorithm," submitted to Proc. IEE, 1987 that the modified Euclidean algorithm mentioned above can be used to solve the Berlekamp-Massey key equation for the errata locator polynomial and the errata evaluator polynomial directly and simultaneously. By this means a new simplified pipeline architecture for both the time and transform domain decoders can be developed for correcting both errors and erasures of RS codes. Such a decoding technique can be faster and simpler than previous methods. See I. S. Reed, T. K. Truong and R. L. Miller, "Decoding of B.C.H. and RS codes with errors and erasures using continued fractions," Electronics Letters, vol. 15, no. 17, Aug. 16, 1976, pp. 542-544. I. S. Reed, T. K. Truong and R. L. Miller, "Simplified algorithm for correcting both errors and erasures of Reed-Solomon codes," Proc. IEE, vol. 126, no. 10, October 1979, pp. 961-963.
In this invention, it is found that the VLSI implementation of the transform domain decoder is simpler than the time domain decoder. However, for a long RS code, due to the large size of the inverse transform unit needed in the transform decoder, the VLSI area needed to implement the transform domain decoder can be substantially larger than that needed for the time domain detector. For moderately long codes, such as the (255,223) RS code used in the concatenated coding system for NASA's Voyager mission, the transform domain decoder is still simpler than the time domain decoder.
The above-mentioned NASA coding system is called the "baseline" system. It used a (7,1/2) convolutional code as its inner code and an 8-bit (255,223) RS code as its outer code. It is shown that this system achieves a bit-error rate (BER) of 10.sup.-6 at a bit signal-to-noise ratio (SNR) of 2.53 dB. See R. L. Miller, L. J. Deutsch and S. A. Butman, "On the error statistics of Viterbi decoding and the performance of concatenated codes," Publication 81-9, Jet Propulsion Laboratory, Pasadena, CA, September 1981.
As noted above, the time domain decoder is more efficient in area than the transform domain decoder for very long RS codes. One such example is the long, 10 bits/symbol (1023,959) RS code being presently considered for very deep space probes. If this code is concatenated with a (15,1/5) convolutional code, it achieves a BER of 10.sup.-6 at a SNR of 0.5 dB. Evidently the new NASA concatenated coding system provides a 2 dB improvement over the present baseline system. See J. H. Yuen and Q. D. Vo, "In search of a 2-dB coding gain," TDA Progress Report 42-83, Jet Propulsion Laboratory, Pasadena, CA, July-September 1985. It is for this reason and many other applications that it is important to develop an efficient, VLSI implementable, time-domain decoder to decode RS codes.
An algorithm was developed by I. S. Reed, T. K. Truong and R. L. Miller, "Decoding of B.C.H. and RS codes with errors and erasures using continued fractions," Electronic Letters, vol. 15, no. 17, Aug. 16, 1976, pp. 542-544 for time domain decoding RS codes to correct both errors and erasures by the use of continued fractions or its equivalent, Euclid's algorithm. This algorithm is a modification of the Berlekamp-Forney method. See G. D. Forney, "On decoding BCH codes," IEEE Trans. on Information Theory, vol. IT-11, 1965, pp. 549-557, and E. R. Berlekamp, Algebraic Coding Theory, McGraw-Hill, 1968. In this algorithm, the continued fraction algorithm is used to find the error locator polynomial from the remainder of the formal power series for the Forney syndrome. The disadvantage of this algorithm is that after the error locator polynomial is obtained by continued fractions, two polynomial multiplications are needed to compute the errata locator polynomial and the errata evaluator polynomial from the known error locator polynomial.